1. Field of the Invention
The present invention relates to encoding and decoding devices and, more particularly, to encoding and decoding devices which are used for a facsimile equipment so as to encode and decode picture information and the like.
2. Description of the Related Art
In encoding a Markov source such as picture information, a technique of predicting a symbol which has not been encoded on the basis of the value of an encoded symbol has recently been adopted. This is a technique of predicting the symbols which are the objects of the current encoding from the values of reference symbols which have already been encoded in the output symbol stream of an information source, classifying the prediction error symbols into several groups according to percentages of accurate prediction which correspond to the values of the reference symbols, and appropriately encoding the prediction error symbols in the respective groups.
Hereinunder, the generation of the prediction error symbols will be referred to as "prediction conversion", the classification of the prediction error symbols into several groups will be referred to as "classification", and the identification data of the group, namely, the index which indicates the percentage of accurate prediction will be referred to as "order". The prediction error symbols which are to be encoded will be referred to as "prediction error symbols". The values of the plurality of reference symbols will be referred to as "reference symbol pattern".
As a method of prediction conversion and the selection of order, an adaptive processing technique which copes with a local change of the statistic nature of an information source is disclosed (Japanese Patent Application No. Hei 1-127134).
As to the technique of encoding the prediction error symbols, a subtraction type arithmetic encoding method is disclosed in, for example, "An Overview of the Basic Principle of the Q-coder Adaptive Binary Arithmetic Coder" (IBM Journal of Research and Development, Vol. 32, No. 6, Nov. 1988) and Japanese Patent Laid-Open No. Hei 2-202267. This method is a kind of number line representation encoding method, in which a symbol list is mapped between 0.0 and 1.0 on a number line and the coordinates are encoded as code words. The subtraction type arithmetic encoding method is characterized by the fact that when the number line is divided in accordance with the produced symbols so as to use the coordinates of the divisions as the code words, the division of the number line is executed only by addition and subtraction.
An example of a conventional process of prediction conversion, classification and encoding will be explained with reference to FIG. 25. In order to make the explanation easy to understand, it is here assumed that the information source is binary image signals, that the reference symbols are the twelve pixels in the neighborhood of the encoding pixel in FIG. 26, Vol. 32, and that the number of classifications (i.e, the number of groups) is sixteen. In other words, it is assumed that twelve pixels have already been encoded and a thirteenth pixel is now being encoded.
In FIG. 25, reference symbols are selected and retrieved from the list of information source symbols 101 by a reference symbol generator 1. In this example, the encoded twelve information source symbols are output as a reference symbol pattern 102. An order and predicted value memory 2 outputs the predicted value 104 and the order 103 of the symbol which is the object of the current encoding operation (this symbol will be referred to as "the encoding symbol" hereinunder) in accordance with the reference symbol pattern 102. A prediction converter 3 generates a prediction error symbol 105 on the basis of the value of the symbol being encoded and the predicted value 104. A region width table 4 converts the order 103 into a region width signal 106 which determines the range allowed to the arithmetic code. An arithmetic coder 5 encodes the prediction error symbol 105 in accordance with the region width signal 106 and outputs a code bit stream. An order and predicted value controller 6 controls the reading and updating operations of the order and predicted value memory 2 on the basis of the prediction error symbol 105.
Since the number of reference symbols is twelve, the order and predicted value memory 2 requires 2.sup.12 order and predicted value table entries, as shown in FIG. 27. Since the number of groups for classification is 16, the order takes a value of 1 to 16 in order to identify the group. It is here assumed that the higher the order is, the higher is the percentage of accurate prediction.
The operation of the conventional process shown in FIG. 25 will now be explained. When the information symbol source symbol 101 (picture signal) is produced from the information source (not shown), the reference symbol generator 1 stores the list of the symbol 101 and selects the signals of the latest twelve encoded pixels and outputs them as the reference symbol pattern 102, as shown in FIG. 26. The order and predicted value memory 2 outputs the predicted value 104 and the order 103 of the encoding symbol from the table shown in FIG. 27 on the basis of the reference symbol pattern 102. The information on the order 103 is converted into the region width signal 106 by the region width table 4 shown in FIG. 28.
The prediction converter 3 obtains the exclusive OR of the encoding symbol 101 in the information source symbol stream and the predicted value 104, and generates the prediction error symbol 105. The prediction error symbol 105 is an MPS (More Probable Symbol) when the prediction is accurate, and an LPS (Less Probable Symbol) when the prediction is wrong. In this example, since the encoding symbol is a binary image signal and the MPS is set at "0" and the LPS at "1", an EX OR gate is used for the prediction converter 3, so that "0" (MPS) is output when the prediction is accurate, and "1" (LPS) is output when the prediction is wrong.
The arithmetic coder 5 maps the prediction error symbol 105 on the number line on the basis of the region width signal 106, thereby executing encoding.
If an i-th symbol is represented by a.sub.i in the prediction error symbol list, and the mapping range (allotted region) of the LPS is represented by S (assigned fixed value by each order), the mapping range (effective region) A.sub.i of the symbol list and the coordinate C.sub.j of the lower boundary thereof at the i th point are updated as follows if the MPS region is taken below the mapping range (effective region) A.sub.i :
When the symbol a.sub.i is an MPS, EQU A.sub.i =A.sub.i-1 -S EQU C.sub.i =C.sub.i-1
When the symbol a.sub.i is an LPS, EQU A.sub.i =S EQU C.sub.i =C.sub.i-1 +(A.sub.i-i -S).
When the effective region A.sub.i is not more than 1/2, A.sub.i is multiplied by an m-th power of 2 in order to enhance the accuracy. At this time, the overflow portion (the portion over the decimal point) of the coordinate C.sub.j is output as a code bit stream. The process of multiplying the effective region A.sub.i by an m-th power of 2 will hereinunder be referred to as "renormalization". The renormalization is represented as follows: EQU Updated A.sub.i =A.sub.i * 2(1/2&lt;update A.sub.i .ltoreq.) EQU Updated C=C* 2.sup.m
In arithmetic encoding, it is known that encoding is realized with high efficiency which is very close to the entropy of the information source by setting the mapping range (allotted region) S at the occurence probability (=prediction error probability) of the LPS. Arithmetic encoding is therefore enabled with high efficiency by the above-described processing if the S value is set in advance so as to be suitable for the percentage of accurate prediction, which corresponds to the order.
FIG. 28 shows an example of the correspondence of an order to a region width. Each value in the table is obtained by multiplying the value in the above-described formula by 2.sup.16.
The adaptive processing of prediction and classification will now be explained.
The order and predicted value controller 6 counts the number of consecutive MPS's and LPS's in the list of the prediction error symbols 105. It can be considered that if k MPS's have been detected, the prediction is more accurate, and that when 1 LPS's have been detected, the prediction has a strong possibility of being wrong. Therefore, the contents of the order and predicted value memory 2 are updated in the following steps in the respective cases. The values k and 1 are set in the order and predicted value controller 6 in advance in accordance with each order.
When 1 LPS's have been detected, it means that the prediction in the reference symbol pattern 102 is wrong.
In this case, the order and predicted value memory 2 subtracts 1 from the order which corresponds to the reference symbol pattern 102 at that time. This operation is executed in order to adapt the order and predicted value to the information source of the symbol which is the object of the current encoding operation by reducing the order, which indicates the percentage of accurate prediction. When the order is the lowest value and further subtraction is impossible, the predicted value is inverted. By this operation, the predicted value having an excessively low percentage of accurate prediction is updated.
When k MPS's have been detected, it means that the prediction in the reference symbol pattern is accurate.
In this case, the order and predicted value memory 2 adds 1 to the order which corresponds to the reference symbol pattern 102 at that time. This operation is executed in order to adapt the order and predicted value to the information source of the symbol which is the object of the current encoding operation by increasing the order, which indicates the percentage of accurate prediction. When the order is the highest value, no addition is executed. According to this operation, it is possible to narrow the region width and suppress the amount of output from the arithmetic coder 5 by increasing the order when the prediction is very accurate. In this way, the order and the predicted value controller 6 updates the contents of the order and predicted value memory 2 in accordance with the statistic nature of the information source, and the arithmetic encoding with a high encoding efficiency is realized.
In this conventional device, a general purpose RAM is essential in the order and predicted value memory 2 because a large capacity (2.sup.12 .times.5 bits, in this example) is required. In arithmetic encoding based on a Markov model, the generation of the reference symbol pattern 102, the retrieval of the order and predicted value memory 2 and the calculation of the region on the number line are executed for each symbol, as is clear from the above explanation. For example, in a standard facsimile equipment, since picture information is encoded at a resolution of 8 horizontal pixels/mm and 7.7 vertical lines/mm, about 1.3 seconds is required for encoding the picture information in an A4 size copy. That is, the processing speed of the conventional device based on a Markov model is much lower than that of an encoding or decoding device based on another coding system such as an MMR encoding system.